
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 2426. -- [HAOI2010]工厂选址 -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>2426: [HAOI2010]工厂选址</h2><span class=green>Time Limit: </span>10 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>128 MB<br><span class=green>Submit: </span>22&nbsp;&nbsp;<span class=green>Solved: </span>14<br>[<a href='submitpage.php?id=2426'>Submit</a>][<a href='problemstatus.php?id=2426'>Status</a>][<a href='bbs.php?id=2426'>Discuss</a>]</center><h2>Description</h2><div class=content><p class="MsoNormal" style="text-align:justify;text-justify:inter-ideograph"><b style="mso-bidi-font-weight:normal"><span lang="RU">某地区有m座煤矿，其中第i号矿每年产量为a<sub>i</sub>吨，现有火力发电厂一个，每年需用煤b吨，每年运行的固定费用（包括折旧费，不包括煤的运费）为h元，每吨原煤从第i号矿运到原有发电厂的运费为C<sub>i0</sub>（i=1，2，&hellip;，m）。 </span></b><b style="mso-bidi-font-weight:normal"><span lang="RU" style="mso-fareast-font-family:宋体;mso-fareast-language:ZH-CN"><o:p></o:p></span></b></p>
<p class="MsoNormal" style="text-align:justify;text-justify:inter-ideograph"><b style="mso-bidi-font-weight:normal"><span lang="RU" style="mso-fareast-font-family:
宋体;mso-fareast-language:ZH-CN"><o:p>&nbsp;</o:p></span></b></p>
<p class="MsoNormal" style="text-align:justify;text-justify:inter-ideograph"><b style="mso-bidi-font-weight:normal"><span lang="RU">现规划新建一个发电厂，m座煤矿每年开采的原煤将全部供给这两座发电厂。现有n个备选的厂址。若在第j号备选厂址建新厂，每年运行的固定费用为h<sub>j</sub>元。每吨原煤从第i号矿运到j号备选厂址的运费为C<sub>ij</sub>（i=1，2，&hellip;，m；j=1，2，&hellip;，n）。 </span></b><b style="mso-bidi-font-weight:normal"><span lang="RU" style="mso-fareast-font-family:宋体;mso-fareast-language:ZH-CN"><o:p></o:p></span></b></p>
<p class="MsoNormal" style="text-align:justify;text-justify:inter-ideograph"><b style="mso-bidi-font-weight:normal"><span lang="RU" style="mso-fareast-font-family:
宋体;mso-fareast-language:ZH-CN"><o:p>&nbsp;</o:p></span></b></p>
<p class="MsoNormal" style="text-align:justify;text-justify:inter-ideograph"><b style="mso-bidi-font-weight:normal"><span lang="RU">试问：应把新厂厂址选取在何处？m座煤矿开采的原煤应如何分配给两个发电厂，才能使每年的总费用（发电厂运行费用与原煤运费之和）为最小。&nbsp;</span></b><b style="mso-bidi-font-weight:normal"><span lang="RU" style="mso-fareast-font-family:宋体;mso-fareast-language:ZH-CN"><o:p></o:p></span></b></p>
<p></p></div><h2>Input</h2><div class=content><p class="MsoNormal" style="margin-left:12.0pt;mso-para-margin-left:1.0gd;
text-align:justify;text-justify:inter-ideograph"><b style="mso-bidi-font-weight:
normal"><span lang="RU">第1行：&nbsp; &nbsp; &nbsp; m&nbsp; b&nbsp; h&nbsp; n <o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left:12.0pt;mso-para-margin-left:1.0gd;
text-align:justify;text-justify:inter-ideograph"><b style="mso-bidi-font-weight:
normal"><span lang="RU">第2行：&nbsp;&nbsp; &nbsp;&nbsp; a<sub>1</sub>&nbsp; a<sub>2</sub> &hellip;&nbsp; a<sub>m</sub> </span></b><b style="mso-bidi-font-weight:normal"><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;;mso-fareast-language:ZH-CN">（</span><span lang="RU">0&lt;=a<sub>i</sub>&lt;=500, a<sub>1</sub>+a<sub>2</sub>+...+a<sub>n</sub>&gt;=b</span></b><b style="mso-bidi-font-weight:normal"><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;;mso-fareast-language:
ZH-CN">）</span></b><b style="mso-bidi-font-weight:normal"><span lang="RU" style="mso-fareast-font-family:宋体;mso-fareast-language:ZH-CN"><o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left:12.0pt;mso-para-margin-left:1.0gd;
text-align:justify;text-justify:inter-ideograph"><b style="mso-bidi-font-weight:
normal"><span lang="RU">第3行： &nbsp; &nbsp;&nbsp; h<sub>1</sub>&nbsp; h<sub>2</sub> &hellip;&nbsp; h<sub>n</sub> </span></b><b style="mso-bidi-font-weight:normal"><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;;mso-fareast-language:ZH-CN">（</span><span lang="RU">0&lt;=h<sub>i</sub>&lt;=100</span></b><b style="mso-bidi-font-weight:normal"><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;;mso-fareast-language:
ZH-CN">）</span></b><b style="mso-bidi-font-weight:normal"><span lang="RU" style="mso-fareast-font-family:宋体;mso-fareast-language:ZH-CN"><o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left:12.0pt;mso-para-margin-left:1.0gd;
text-align:justify;text-justify:inter-ideograph"><b style="mso-bidi-font-weight:
normal"><span lang="RU">第4行：&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; C<sub>10</sub> C<sub>20</sub> &hellip; C<sub>m0</sub> </span></b><b style="mso-bidi-font-weight:normal"><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;;mso-fareast-language:ZH-CN">（</span><span lang="RU">0&lt;=Cij&lt;=50</span></b><b style="mso-bidi-font-weight:normal"><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;;mso-fareast-language:
ZH-CN">）</span><span lang="RU"> <o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left:12.0pt;mso-para-margin-left:1.0gd;
text-align:justify;text-justify:inter-ideograph"><b style="mso-bidi-font-weight:
normal"><span lang="RU">第5行：&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; C<sub>11</sub> C<sub>21</sub> &hellip; C<sub>m1</sub> <o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left:12.0pt;mso-para-margin-left:1.0gd;
text-align:justify;text-justify:inter-ideograph"><b style="mso-bidi-font-weight:
normal"><span lang="RU">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &hellip;&nbsp;&nbsp; &hellip; <o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left:12.0pt;mso-para-margin-left:1.0gd;
text-align:justify;text-justify:inter-ideograph"><b style="mso-bidi-font-weight:
normal"><span lang="RU">第</span></b><b style="mso-bidi-font-weight:normal"><span lang="RU" style="mso-fareast-font-family:宋体;mso-fareast-language:ZH-CN">n</span><span lang="RU">+4行：C<sub>1n</sub> C<sub>2n</sub> &hellip; C<sub>mn</sub> <o:p></o:p></span></b></p>
<p></p></div><h2>Output</h2><div class=content><p class="MsoNormal" style="margin-left:12.0pt;mso-para-margin-left:1.0gd;
text-align:justify;text-justify:inter-ideograph"><b style="mso-bidi-font-weight:
normal"><span lang="RU">第1行：新厂址编号，如果有多个编号满足要求，输出最小的。 <o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left:12.0pt;mso-para-margin-left:1.0gd;
text-align:justify;text-justify:inter-ideograph"><b style="mso-bidi-font-weight:
normal"><span lang="RU">第2行：总费用&nbsp;<o:p></o:p></span></b></p>
<p></p></div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>4 2 7 9 <br />
3 1 10 3 <br />
6 3 7 1 10 2 7 4 9 <br />
1 2 4 3 <br />
6 6 8 2 <br />
4 10 8 4 <br />
10 2 9 2 <br />
7 6 6 2 <br />
9 3 7 1 <br />
2 1 6 9 <br />
3 1 10 9 <br />
4 2 1 8 <br />
2 1 3 4 <br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>8 <br />
49 <br />
</span></div><h2>HINT</h2>
			<div class=content><p><p class="MsoNormal" style="margin-left:24.0pt;mso-para-margin-left:2.0gd;<br />
text-align:justify;text-justify:inter-ideograph"><b style="mso-bidi-font-weight:<br />
normal"><span lang="RU">对于所有数据, n&lt;=50, m&lt;=50000, b&lt;=10000&nbsp;<o:p></o:p></span></b></p><br />
<p></p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Day2'>Day2</a></p></div><center>[<a href='submitpage.php?id=2426'>Submit</a>][<a href='problemstatus.php?id=2426'>Status</a>][<a href='bbs.php?id=2426'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
